package LQB;
/*
小明走楼梯，还剩39阶台阶，小明走1阶或者2阶，左脚先走，最后到的时候是右脚，请问有多少总走法
 */
public class 第39阶台阶 {
    public static void main(String[] args) {
        f(39,0);
        System.out.println(count);
    }
    static int count=0;
    public static void f(int n,int step){//n表示剩下的台阶，step已走的台阶
        if (n<0){
            return;
        }
        if (n==0){
            if (step%2==0){//判断到的时候是不是右脚先到
                count++;
            }
        }
        f(n-1,step+1);//走1阶
        f(n-2,step+1);//走2阶
    }
}
